{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Stone Game VIII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #dynamic-programming #game-theory #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #动态规划 #博弈 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: stoneGameVIII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #石子游戏 VIII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>Alice 和 Bob 玩一个游戏，两人轮流操作， <strong>Alice 先手</strong> 。</p>\n",
    "\n",
    "<p>总共有 <code>n</code> 个石子排成一行。轮到某个玩家的回合时，如果石子的数目 <strong>大于 1</strong> ，他将执行以下操作：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>选择一个整数 <code>x &gt; 1</code> ，并且 <strong>移除</strong> 最左边的 <code>x</code> 个石子。</li>\n",
    "\t<li>将<strong> 移除</strong> 的石子价值之 <strong>和</strong> 累加到该玩家的分数中。</li>\n",
    "\t<li>将一个 <strong>新的石子</strong> 放在最左边，且新石子的值为被移除石子值之和。</li>\n",
    "</ol>\n",
    "\n",
    "<p>当只剩下 <strong>一个</strong> 石子时，游戏结束。</p>\n",
    "\n",
    "<p>Alice 和 Bob 的 <strong>分数之差</strong> 为 <code>(Alice 的分数 - Bob 的分数)</code> 。 Alice 的目标是<strong> 最大化</strong> 分数差，Bob 的目标是 <strong>最小化</strong> 分数差。</p>\n",
    "\n",
    "<p>给你一个长度为 <code>n</code> 的整数数组 <code>stones</code> ，其中 <code>stones[i]</code> 是 <strong>从左边起</strong> 第 <code>i</code> 个石子的价值。请你返回在双方都采用 <strong>最优</strong> 策略的情况下，Alice 和 Bob 的 <strong>分数之差</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>stones = [-1,2,-3,4,-5]\n",
    "<b>输出：</b>5\n",
    "<strong>解释：</strong>\n",
    "- Alice 移除最左边的 4 个石子，得分增加 (-1) + 2 + (-3) + 4 = 2 ，并且将一个价值为 2 的石子放在最左边。stones = [2,-5] 。\n",
    "- Bob 移除最左边的 2 个石子，得分增加 2 + (-5) = -3 ，并且将一个价值为 -3 的石子放在最左边。stones = [-3] 。\n",
    "两者分数之差为 2 - (-3) = 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>stones = [7,-6,5,10,5,-2,-6]\n",
    "<b>输出：</b>13\n",
    "<b>解释：</b>\n",
    "- Alice 移除所有石子，得分增加 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 ，并且将一个价值为 13 的石子放在最左边。stones = [13] 。\n",
    "两者分数之差为 13 - 0 = 13 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>stones = [-10,-12]\n",
    "<b>输出：</b>-22\n",
    "<strong>解释：</strong>\n",
    "- Alice 只有一种操作，就是移除所有石子。得分增加 (-10) + (-12) = -22 ，并且将一个价值为 -22 的石子放在最左边。stones = [-22] 。\n",
    "两者分数之差为 (-22) - 0 = -22 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == stones.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= stones[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [stone-game-viii](https://leetcode.cn/problems/stone-game-viii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [stone-game-viii](https://leetcode.cn/problems/stone-game-viii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-1,2,-3,4,-5]', '[7,-6,5,10,5,-2,-6]', '[-10,-12]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        total=sum(stones)\n",
    "        dp=total\n",
    "        for i in range(len(stones)-1,1,-1):\n",
    "            total-=stones[i]\n",
    "            dp=max(dp,total-dp)\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        s = list(accumulate(stones))\n",
    "        n = len(stones)\n",
    "        dp = s[-1]  #  从后向前，dp表示当前遍历到的所有stones后缀的，先手的最大差值 的最大值\n",
    "        # dp[-1] = 0\n",
    "        # dp[-2] = s[n-1]\n",
    "        # dp[-3] = max(s[n-1],s[n-2]-dp[-2]) = max(dp[-2],s[n-2]-dp[-2])\n",
    "        # dp[-4] = max(s[n-1],s[n-2]-dp[-2],s[n-3]-dp[-3]) = max(dp[-3],s[n-3]-dp[-3])\n",
    "        # ...\n",
    "        # dp[-2] = s[n-1], 从dp[-3] 开始推\n",
    "        for i in range(n - 3, -1, -1):\n",
    "            dp = max(dp, s[i + 1] - dp)\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        s = sum(stones)\n",
    "        res = s\n",
    "        for i in range(n-1, 1, -1):\n",
    "            s -= stones[i]\n",
    "            res = max(res, s - res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        for i in range(1, len(stones)):\n",
    "            stones[i] += stones[i - 1]\n",
    "        post_max = stones[-1]\n",
    "        for i in range(len(stones) - 2, 0, -1):\n",
    "            stones[i] -= post_max\n",
    "            post_max = max(post_max, stones[i])\n",
    "        return max(stones[1:])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        if len(stones) == 2:\n",
    "            return sum(stones)\n",
    "\n",
    "        best = [None for _ in stones]\n",
    "        best[-1] = S = sum(stones) # no other choice\n",
    "\n",
    "        best_diff = -inf\n",
    "        S_right = 0\n",
    "        for i in range(len(stones)-2, 0, -1):\n",
    "            S_right += stones[i+1]\n",
    "            if best_diff < S - S_right - best[i+1]:\n",
    "                best_diff = S - S_right - best[i+1]\n",
    "            best[i] = max(S, best_diff)\n",
    "        return best[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        total=sum(stones)\n",
    "        dp=total\n",
    "        for i in range(len(stones)-1,1,-1):\n",
    "            total-=stones[i]\n",
    "            dp=max(dp,total-dp)\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        pre = [stones[0]] * n\n",
    "        for i in range(1, n):\n",
    "            pre[i] = pre[i - 1] + stones[i]\n",
    "        ans = pre[-1]\n",
    "        for i in range(n - 2, 0, -1):\n",
    "            ans = max(ans, pre[i] - ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        # Calculate prefix sum\n",
    "        for i in range(1, len(stones)):\n",
    "            stones[i] += stones[i - 1]\n",
    "\n",
    "        # Initialize dp array with last stone value\n",
    "        dp = stones[-1]\n",
    "\n",
    "        # Start decision from second last stone\n",
    "        for i in range(len(stones) - 2, 0, -1):\n",
    "            dp = max(dp, stones[i] - dp)\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "#         # 移除并放回，前缀和不变\n",
    "#         # 每次拿的石子必然包括前面的前缀和\n",
    "#         @lru_cache(None)\n",
    "#         def dfs(idx):\n",
    "#             if idx >= n - 1:\n",
    "#                 return presum[n]\n",
    "#             # 不选当前坐标，选后面的会是dfs(idx+1),选当前坐标会得到presum[idx+1] - dfs(idx+1)。取两者最大值\n",
    "#             return max(dfs(idx + 1), presum[idx + 1] - dfs(idx+1))\n",
    "\n",
    "#         n = len(stones)\n",
    "#         presum = list(accumulate(stones,initial=0))\n",
    "#         return dfs(1)\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        f = [0] * n\n",
    "        pre = list(accumulate(stones))\n",
    "        f[-1] = pre[-1]\n",
    "        for i in range(n-2,0,-1):\n",
    "            f[i] = max(f[i+1],pre[i]-f[i+1])\n",
    "        return f[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "#         # 移除并放回，前缀和不变\n",
    "#         # 每次拿的石子必然包括前面的前缀和\n",
    "#         @lru_cache(None)\n",
    "#         def dfs(idx):\n",
    "#             if idx >= n - 1:\n",
    "#                 return presum[n]\n",
    "#             # 不选当前坐标，选后面的会是dfs(idx+1),选当前坐标会得到presum[idx+1] - dfs(idx+1)。取两者最大值\n",
    "#             return max(dfs(idx + 1), presum[idx + 1] - dfs(idx+1))\n",
    "\n",
    "#         n = len(stones)\n",
    "#         presum = list(accumulate(stones,initial=0))\n",
    "#         return dfs(1)\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        f = [0] * n\n",
    "        pre = list(accumulate(stones))\n",
    "        f[-1] = pre[-1]\n",
    "        for i in range(n-2,0,-1):\n",
    "            f[i] = max(f[i+1],pre[i]-f[i+1])\n",
    "        return f[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "#         # 移除并放回，前缀和不变\n",
    "#         # 每次拿的石子必然包括前面的前缀和\n",
    "#         @lru_cache(None)\n",
    "#         def dfs(idx):\n",
    "#             if idx >= n - 1:\n",
    "#                 return presum[n]\n",
    "#             # 不选当前坐标，选后面的会是dfs(idx+1),选当前坐标会得到presum[idx+1] - dfs(idx+1)。取两者最大值\n",
    "#             return max(dfs(idx + 1), presum[idx + 1] - dfs(idx+1))\n",
    "\n",
    "#         n = len(stones)\n",
    "#         presum = list(accumulate(stones,initial=0))\n",
    "#         return dfs(1)\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        pre = list(accumulate(stones))\n",
    "        f = [0] * n\n",
    "        f[n - 1] = pre[n - 1]\n",
    "        for i in range(n - 2, 0, -1):\n",
    "            f[i] = max(f[i + 1], pre[i] - f[i + 1])\n",
    "        return f[1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        pre = [stones[0]] * n\n",
    "        for i in range(1, n):\n",
    "            pre[i] = pre[i - 1] + stones[i]\n",
    "        score = [pre[-1]] * n\n",
    "        for i in range(n - 2, 0, -1):\n",
    "            score[i] = max(score[i + 1], pre[i] - score[i + 1])\n",
    "        return score[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        #dp[i]表示先手者在区间[i,n)内选择能达到的最大分差\n",
    "        pre = list(accumulate(stones))\n",
    "        n = len(stones)\n",
    "        dp = [0]*n\n",
    "        dp[n-1] = pre[n-1]\n",
    "        for i in range(n-2, 0, -1):\n",
    "            dp[i] = max(dp[i+1], pre[i]-dp[i+1])\n",
    "        return dp[1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        \n",
    "        n=len(stones)\n",
    "        pre=[0]*n\n",
    "        pre[0]=stones[0]\n",
    "        for i in range(1,n):\n",
    "            pre[i]=pre[i-1]+stones[i]\n",
    "        \n",
    "        dp=[0]*n\n",
    "        dp[-1]=pre[-1]\n",
    "        ans=dp[-1]\n",
    "        for i in range(n-2,0,-1):\n",
    "            dp[i]=max(dp[i+1],pre[i]-dp[i+1])\n",
    "            ans=max(ans,dp[i])\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        s = list(accumulate(stones))\n",
    "        f = s[-1]\n",
    "        for i in range(len(s) - 2, 0, -1):\n",
    "            f = max(f, s[i] - f)\n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "#         # 移除并放回，前缀和不变\n",
    "#         # 每次拿的石子必然包括前面的前缀和\n",
    "#         @lru_cache(None)\n",
    "#         def dfs(idx):\n",
    "#             if idx >= n - 1:\n",
    "#                 return presum[n]\n",
    "#             # 不选当前坐标，选后面的会是dfs(idx+1),选当前坐标会得到presum[idx+1] - dfs(idx+1)。取两者最大值\n",
    "#             return max(dfs(idx + 1), presum[idx + 1] - dfs(idx+1))\n",
    "\n",
    "#         n = len(stones)\n",
    "#         presum = list(accumulate(stones,initial=0))\n",
    "#         return dfs(1)\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        f = [0] * n\n",
    "        pre = list(accumulate(stones))\n",
    "        f[-1] = pre[-1]\n",
    "        for i in range(n-2,0,-1):\n",
    "            f[i] = max(f[i+1],pre[i]-f[i+1])\n",
    "        return f[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        for i in range(1, n):\n",
    "            stones[i] += stones[i - 1]\n",
    "        dp = [int(-2e9) for _ in range(n)]\n",
    "        dpmi = [0 for _ in range(n)]\n",
    "        dp[n - 1] = stones[n - 1]\n",
    "        mi = -stones[n - 1]\n",
    "        if n - 2 > 0:\n",
    "            dp[n - 2] = mi + stones[n - 2]\n",
    "            dp[n - 2] = max(dp[n - 2], dp[n - 1]) \n",
    "        for i in reversed(range(1, n - 2)):\n",
    "            mi = min(mi, dp[i + 2] - stones[i + 1])\n",
    "            dp[i] = mi + stones[i]\n",
    "            dp[i] = max(dp[i], dp[i + 1])\n",
    "        return dp[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        ps = [0] + list(accumulate(stones))\n",
    "        # @cache\n",
    "        # def dfs(u):\n",
    "        #     if u == n - 1: return ps[n]\n",
    "        #     return max(dfs(u + 1), ps[u + 1] - dfs(u + 1))\n",
    "        # return dfs(1)\n",
    "        f = [0] * (n + 1)\n",
    "        f[-1] = ps[-1]\n",
    "        for i in range(n - 1, 1, -1):\n",
    "            f[i] = max(f[i + 1], ps[i] - f[i + 1])\n",
    "        return f[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        for i in range(1, n):\n",
    "            stones[i] += stones[i - 1]\n",
    "        dp = [int(-2e9) for _ in range(n)]\n",
    "        dpmi = [0 for _ in range(n)]\n",
    "        dp[n - 1] = stones[n - 1]\n",
    "        mi = -stones[n - 1]\n",
    "        if n - 2 > 0:\n",
    "            dp[n - 2] = mi + stones[n - 2]\n",
    "            dp[n - 2] = max(dp[n - 2], dp[n - 1]) \n",
    "        for i in reversed(range(1, n - 2)):\n",
    "            mi = min(mi, dp[i + 2] - stones[i + 1])\n",
    "            dp[i] = mi + stones[i]\n",
    "            dp[i] = max(dp[i], dp[i + 1])\n",
    "        return dp[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        for i in range(1, n):\n",
    "            stones[i] += stones[i - 1]\n",
    "        dp = [int(-2e9) for _ in range(n)]\n",
    "        dpmi = [0 for _ in range(n)]\n",
    "        dp[n - 1] = stones[n - 1]\n",
    "        mi = -stones[n - 1]\n",
    "        dp[n - 2] = mi + stones[n - 2]\n",
    "        dp[n - 2] = max(dp[n - 2], dp[n - 1]) \n",
    "        for i in reversed(range(1, n - 2)):\n",
    "            mi = min(mi, dp[i + 2] - stones[i + 1])\n",
    "            dp[i] = mi + stones[i]\n",
    "            dp[i] = max(dp[i], dp[i + 1])\n",
    "        return dp[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        acc = list(accumulate(stones))\n",
    "        n = len(stones)\n",
    "        f = [0] * n \n",
    "        f[-1] = acc[-1]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            f[i] = max(acc[i] - f[i + 1], f[i + 1])\n",
    "        return f[1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        for i in range(1, n):\n",
    "            stones[i] += stones[i - 1]\n",
    "        dp = [int(-2e9) for _ in range(n)]\n",
    "        dpmi = [0 for _ in range(n)]\n",
    "        dp[n - 1] = stones[n - 1]\n",
    "        mi = -stones[n - 1]\n",
    "        if n - 2 > 0:\n",
    "            dp[n - 2] = mi + stones[n - 2]\n",
    "            dp[n - 2] = max(dp[n - 2], dp[n - 1]) \n",
    "        for i in reversed(range(1, n - 2)):\n",
    "            mi = min(mi, dp[i + 2] - stones[i + 1])\n",
    "            dp[i] = mi + stones[i]\n",
    "            dp[i] = max(dp[i], dp[i + 1])\n",
    "        return dp[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        for i in range(1, n):\n",
    "            stones[i] += stones[i - 1]\n",
    "        dp = [int(-2e9) for _ in range(n)]\n",
    "        dpmi = [0 for _ in range(n)]\n",
    "        dp[n - 1] = stones[n - 1]\n",
    "        mi = -stones[n - 1]\n",
    "        dp[n - 2] = mi + stones[n - 2]\n",
    "        dp[n - 2] = max(dp[n - 2], dp[n - 1]) \n",
    "        for i in reversed(range(1, n - 2)):\n",
    "            mi = min(mi, dp[i + 2] - stones[i + 1])\n",
    "            dp[i] = mi + stones[i]\n",
    "            dp[i] = max(dp[i], dp[i + 1])\n",
    "        return dp[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        S = stones[::]\n",
    "        for i in range(1, n):\n",
    "            S[i] += S[i-1]\n",
    "\n",
    "        dp1 = [-0x7fffffff] * n\n",
    "        dp2 = [0x7fffffff] * n\n",
    "        dp1[n-1] = S[n-1]\n",
    "        dp2[n-1] = -S[n-1]\n",
    "\n",
    "        min_dp1 = -S[n-1]\n",
    "        max_dp2 = S[n-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if i == 0:\n",
    "                dp1[i] = max_dp2\n",
    "            else:\n",
    "                max_dp2 = max(max_dp2, S[i] + dp2[i+1])\n",
    "                dp1[i] = max_dp2\n",
    "\n",
    "            if i == 0:\n",
    "                dp2[i] = min_dp1\n",
    "            else:\n",
    "                min_dp1 = min(min_dp1, dp1[i+1] - S[i])\n",
    "                dp2[i] = min_dp1\n",
    "\n",
    "        return dp1[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        pre = list(itertools.accumulate(stones)) \n",
    "        n = len(stones)\n",
    "        dp = [-sys.maxsize] * n     \n",
    "        for ith in range(n-1, 0, -1):\n",
    "            dp[ith] = max(dp[ith + 1], pre[ith] - dp[ith+1]) if ith < n-1 else pre[ith]\n",
    "\n",
    "        return dp[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        pre = list(itertools.accumulate(stones)) \n",
    "        n = len(stones)\n",
    "        dp = [-sys.maxsize] * n     \n",
    "        for ith in range(n-1, 0, -1):\n",
    "            dp[ith] = max(dp[ith + 1], pre[ith] - dp[ith+1]) if ith < n-1 else pre[ith]\n",
    "\n",
    "        return dp[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        S = stones[::]\n",
    "        for i in range(1, n):\n",
    "            S[i] += S[i-1]\n",
    "\n",
    "        dp1 = [-0x7fffffff] * n\n",
    "        dp2 = [0x7fffffff] * n\n",
    "        dp1[n-1] = S[n-1]\n",
    "        dp2[n-1] = -S[n-1]\n",
    "\n",
    "        min_dp1 = -S[n-1]\n",
    "        max_dp2 = S[n-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if i == 0:\n",
    "                dp1[i] = max_dp2\n",
    "            else:\n",
    "                max_dp2 = max(max_dp2, S[i] + dp2[i+1])\n",
    "                dp1[i] = max_dp2\n",
    "\n",
    "            if i == 0:\n",
    "                dp2[i] = min_dp1\n",
    "            else:\n",
    "                min_dp1 = min(min_dp1, dp1[i+1] - S[i])\n",
    "                dp2[i] = min_dp1\n",
    "\n",
    "        return dp1[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        a,b=0,0\n",
    "        n=len(stones)\n",
    "        pre=[0]*(n+1)\n",
    "        for i in range(n):\n",
    "            pre[i+1]=pre[i]+stones[i]\n",
    "        pre=pre[1:]\n",
    "        dp=[0]*n\n",
    "        dp[-1]=pre[-1]\n",
    "        for i in range(n-2,0,-1):\n",
    "            dp[i]=max(dp[i+1],pre[i]-dp[i+1])\n",
    "        print(dp)\n",
    "        return dp[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        l = len(stones)\n",
    "        s = [stones[0]] * l\n",
    "        for i in range(1, l):\n",
    "            s[i] = stones[i] + s[i - 1]\n",
    "        dp = [0] * (l - 1) + [s[-1]]\n",
    "        right = s[-1]\n",
    "        for i in range(l - 2, -1, -1):\n",
    "            dp[i] = s[i] - right\n",
    "            right = max(right, dp[i])\n",
    "        return max(dp[1:])\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        N = len(stones)\n",
    "        pre = [stones[0]]*N\n",
    "        for i in range(1,N):\n",
    "            pre[i] = pre[i-1]+stones[i]\n",
    "        dp = [ [0]*2 for i in range(N+1)]\n",
    "        dp[N-1] = [pre[-1],pre[-1]]\n",
    "        ret = 0\n",
    "        for i in range(N-2,0,-1):\n",
    "            right,subdiff = dp[i+1]\n",
    "            left = right-subdiff+pre[i]\n",
    "            # print(left,right,subdiff)\n",
    "            if left-right>subdiff:\n",
    "                diff = left-right\n",
    "            else:\n",
    "                left = right \n",
    "                diff=subdiff\n",
    "            dp[i] = [left,diff]\n",
    "        # print(pre,dp)\n",
    "        return dp[1][1] \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        ps = list(accumulate(stones, initial=0))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx):\n",
    "            if idx == n - 1:\n",
    "                return ps[-1]\n",
    "            \n",
    "            return max(dfs(idx + 1), ps[idx + 1] - dfs(idx + 1))\n",
    "        \n",
    "        ans = dfs(1)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        # 移除并放回，前缀和不变\n",
    "        # 每次拿的石子必然包括前面的前缀和\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx):\n",
    "            if idx >= n - 1:\n",
    "                return presum[n]\n",
    "            # 不选当前坐标，选后面的会是dfs(idx+1),选当前坐标会得到presum[idx+1] - dfs(idx+1)。取两者最大值\n",
    "            return max(dfs(idx + 1), presum[idx + 1] - dfs(idx+1))\n",
    "\n",
    "        n = len(stones)\n",
    "        presum = list(accumulate(stones,initial=0))\n",
    "        return dfs(1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        if n == 2:\n",
    "            return sum(stones)\n",
    "\n",
    "        p = list(accumulate(stones))\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == n - 1:\n",
    "                return p[-1]\n",
    "            res = max(dfs(i + 1), p[i] - dfs(i + 1))\n",
    "            return res\n",
    "\n",
    "        return dfs(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        pre = list(accumulate(stones))\n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i == n-1:\n",
    "                return pre[i]\n",
    "\n",
    "            return max(f(i+1), pre[i]-f(i+1))\n",
    "        return f(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameVIII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        pre = list(accumulate(stones))\n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i == n-1:\n",
    "                return pre[i]\n",
    "\n",
    "            return max(f(i+1), pre[i]-f(i+1))\n",
    "        return f(1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
